package cn.mayday.algorithms.year2021.month1.map;

import java.util.LinkedHashMap;
import java.util.Map;

/**
 * 剑指 Offer 50. 第一个只出现一次的字符
 * 在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
 *
 * @author Mayday05
 * @date 2021/5/12 14:10
 */
public class Offer50FirstUniqChar {

    public static void main(String[] args) {

    }

//    map遍历一遍保存个数
//    for循环字符串，判断第一个个数为1的break
//
//    时间复杂度N
//    空间复杂度N

//    优化点：第二次for循环时，可以不for循环字符串，改为使用有序的LinkedHashMap，由于字母顺序有限26个，
//    不随N线程增加，当字符串长度较长时，能够一定程度上减少


    public char firstUniqChar(String s) {
        Map<Character, Boolean> map = new LinkedHashMap<>();

        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), false);
            } else {
                map.put(s.charAt(i), true);
            }
        }

        for (Map.Entry<Character, Boolean> temp : map.entrySet()) {
            if (temp.getValue()) {
                return temp.getKey();
            }
        }
        return ' ';
    }
}
